package everydayone.merge;

import java.util.Arrays;

/**
 * @Date 2020/04/16
 * @author 王光浩
 * @Thinking 先排序，后遍历
 * @Analysis 时间复杂度O（nlogn），空间复杂度O（n）
 */
public class MyMethodTwo {
	/**
	 * 对数组按照第一个元素进行排序
	 * @param left
	 * @param right
	 * @param target
	 */
	private void helper(int left,int right,int[][] target) {
		if(right-left <= 0) return;
		int l = left;
		int r = right;
		int[] tem = target[l];
		while(l<r) {
			while(r>l && target[r][0]>=tem[0]) r--;
			target[l] = target[r];
			while(r>l && target[l][0]<tem[0]) l++;
			target[r] = target[l];			
		}
		target[l] = tem;
		helper(left,l-1,target);
		helper(l+1,right,target);
	}
	public int[][] merge(int[][] intervals) {
		helper(0,intervals.length-1,intervals);
		int[][] ret = new int[intervals.length][];
		int index=-1;
		//将有交集的区间进行合并
		for(int i = 0; i<intervals.length ; i++) {
			//不存在交集不需要合并
			if(index == 0 || ret[index][1]<intervals[i][0]) ret[++index]=intervals[i];
			//存在交集，需要合并
			else {
				ret[index][0] = Math.min(ret[index][0], intervals[i][0]);
				ret[index][1] = Math.max(ret[index][1], intervals[i][1]);
			}
		}
		return Arrays.copyOf(ret, index+1);
	}
}
